import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:数组问题
 * User: LXW
 * Date: 2022-02-22
 * Time: 12:31
 */
// 1.
/*寻找数组的中心索引
        给你一个整数数组 nums ，请计算数组的 中心下标 。

        数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

        如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

        如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。*/
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++) {
            sum += nums[i];
        }
        int liftSum = 0;
        for(int j = 0;j < nums.length;j++) {
            if(liftSum == sum-liftSum-nums[j]) {
                return j;
            }
            liftSum += nums[j];
        }
        return -1;
    }
}
// 2.
/*搜索插入位置
        给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

        请必须使用时间复杂度为 O(log n) 的算法。*/
class Solution2 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                left = mid + 1;
            }
            if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;
    }
}
public class Test {
    // 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
    //在「杨辉三角」中，每个数是它左上方和右上方的数的和
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1);
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for (int j = 1; j < i; j++) {
                List<Integer> tmp = ret.get(i-1);
                int num = tmp.get(j) + tmp.get(j-1);
                list.add(num);
            }
            list.add(1);
            ret.add(list);
        }
        return ret;
    }
    public static void main(String[] args) {

    }
}
